package com.gitee.huanminabc.utils_common.dsa.data_structure.ky;

import com.gitee.huanminabc.utils_common.dsa.data_structure.tree.rbtree.RBTree;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.function.BiFunction;
import java.util.function.Function;

/**
 * 无冲突哈希表(线程安全)
 * 原来的HashMap是链表+红黑树 在并发情况下会可能会导致死循环的情况。
 * 因为在resize的时候,因为多个线程同时扩容,导致链表的顺序被打乱,导致线程当前节点的下一个节点是自己,导致死循环
 * <p>
 * 这里解决办法就是扩容的时候加锁,保证链表的顺序不会被打乱
 * <p>
 *  性能和ConcurrentHashMap几乎一样, 我们也是使用分段锁,但是我们的分段锁是根据key的hash值来分段的,而不是固定的
 *  这样可以保证在并发情况下,同一个key的操作是串行的,而不是并行的
 *  没啥用,只是为了学习还是使用ConcurrentHashMap吧
 */
public class HashThreadMap<K extends Comparable<K>, V> implements Map<K, V> {

    private volatile Root[] nodes;
    private  AtomicInteger size = new AtomicInteger(0);
    private volatile int capacity = 16;
    //读写锁
    private final ReentrantReadWriteLock reentrantReadWriteLock = new ReentrantReadWriteLock();

    private static class Root<K extends Comparable<K>, V> {
        //长度,大于8就转红黑树,如果长度小于6就转链表 ,如果正在发送扩容那么就不转等待下次满足条件再转
        int length;
        //红黑树
        RBTree<ChildNode<K, V>> rbTree;
        //链表
        ChildNode<K, V> node;

    }

    private static class ChildNode<K extends Comparable<K>, V> implements Comparable<ChildNode<K, V>> {
        K key;
        V value;
        ChildNode<K, V> next;

        public ChildNode() {
        }

        public ChildNode(K key) {
            this.key = key;
        }

        @Override
        public int compareTo(ChildNode<K, V> o) {
            if (o == null) {
                return 1;
            }
            if (key == null) {
                return -1;
            }
            return key.compareTo(o.key);
        }
    }


    public HashThreadMap() {
        nodes = new Root[capacity];
        for (int i = 0; i < capacity; i++) {
            nodes[i] = new Root<>();
        }
    }
    public HashThreadMap(int capacity) {
        this.capacity = capacity;
        nodes = new Root[capacity];
        for (int i = 0; i < capacity; i++) {
            nodes[i] = new Root<>();
        }
    }

    private int hash(Object key) {
        return key.hashCode() & 0x7FFFFFFF % this.capacity;
    }
    private int hash(Object key, int capacity) {
        return key.hashCode() & 0x7FFFFFFF % capacity;
    }
    private V putInside(K key, V value) {
        resize();
        try {
            reentrantReadWriteLock.readLock().lock();
            //判断是红黑树还是链表
            int index = hash(key);
            Root<K, V> root = this.nodes[index];
            synchronized (root) {
                V v = null;
                if (root.node == null && root.rbTree == null) {
                    v = putNode(key, value, root);
                } else if (root.rbTree != null) {
                    v = putTree(key, value, root);
                } else {
                    v = putNode(key, value, root);
                }
                return v;
            }
        } finally {
            reentrantReadWriteLock.readLock().unlock();
        }
    }

    private V putTree(K key, V value, Root<K, V> root) {
            //判断是否存在
            ChildNode<K, V> childNode = new ChildNode<>(key);
            RBTree<ChildNode<K, V>>.RBTNode<ChildNode<K, V>> search = root.rbTree.search(childNode);
            if (search != null) {
                search.getKey().value = value;
                return  search.getKey().value;
            }
            ChildNode<K, V> childNode2 = new ChildNode<>();
            childNode2.key = key;
            childNode2.value = value;
            root.rbTree.insert(childNode2);
            root.length++;
            size.incrementAndGet();
            autoChange(root);//自动转换
            return value;
    }

    private V putNode(K key, V value, Root<K, V> root) {
            ChildNode<K, V> optNode = root.node;//取出头节点
            //找到最后一个节点
            while (optNode != null) {
                //判断是否存在,存在就替换
                if (optNode.key.equals(key)) {
                    optNode.value = value;
                    return value;
                }
                ChildNode<K, V> nodeSwap = optNode.next;
                //如果是空就跳出
                if (nodeSwap == null) {
                    break;
                }
                optNode = nodeSwap;
            }
            //创建新节点
            ChildNode<K, V> newNode = new ChildNode<>();
            newNode.key = key;
            newNode.value = value;
            //插入到最后一个节点
            if (optNode == null) {//表示头节点是空的
                root.node = newNode;
            } else {//插入到最后一个节点
                optNode.next = newNode;
            }
            root.length++;
            size.incrementAndGet();
            autoChange(root);//自动转换
        return value;
    }

    //返回的是旧值
    @Override
    public V remove(Object key) {
        try {
            reentrantReadWriteLock.readLock().lock();
            int index = hash(key);
            Root<K, V> root = this.nodes[index];
            synchronized (root) {
                if (root.rbTree != null) {
                    return removeTree((K) key, root);
                } else if (root.node != null) {
                    return removeNode((K) key, root);
                }
                return null;
            }
        } finally {
            reentrantReadWriteLock.readLock().unlock();
        }
    }

    private V removeTree(K key,Root<K, V> root) {
            ChildNode<K, V> childNode = new ChildNode<>(key);
            RBTree<ChildNode<K, V>>.RBTNode<ChildNode<K, V>> search = root.rbTree.search(childNode);
            if (search != null) {
                ChildNode<K, V> key1 = search.getKey();
                root.rbTree.remove(key1);
                size.decrementAndGet();
                root.length--;
                autoChange(root);
                return key1.value;
            }
            return null;
    }

    private V removeNode(K key, Root<K, V> root) {
            //父节点
            ChildNode<K, V> preNode = root.node;
            //判断父节点是否满足
            if (preNode.key.equals(key)) {
                root.node = preNode.next;
                size.decrementAndGet();
                root.length--;
                autoChange(root);
                return preNode.value;
            }
            ChildNode<K, V> optNode = root.node.next;
            while (optNode != null) {
                if (optNode.key.equals(key)) {
                    preNode.next = optNode.next;
                    size.decrementAndGet();
                    root.length--;
                    autoChange(root);
                    return optNode.value;
                }
                preNode = optNode;
                optNode = optNode.next;
            }
            return null;
    }


    //扩容
    private void resize() {
        if (size.get() > capacity * 0.75) {
            try {
                reentrantReadWriteLock.writeLock().lock();
                if (size.get() > capacity * 0.75) {
                    int newCapacity = capacity * 2;
                    Root[] newNodes = new Root[newCapacity];
                    for (int i = 0; i < newCapacity; i++) {
                        newNodes[i] = new Root<>();
                    }
                    for (Root root : nodes) {
                        //如果节点是红黑树,那么转换为链表然后在重新计算
                        if(root.rbTree!=null){
                            RBTree rbTree = root.rbTree;
                            List<ChildNode<K, V>> list = rbTree.toList();
                            ChildNode<K, V> head = new ChildNode<>();
                            head.key = list.get(0).key;
                            head.value = list.get(0).value;
                            ChildNode<K, V> temp = head;
                            for (int i = 1; i < list.size(); i++) {
                                ChildNode<K, V> childNode = list.get(i);
                                childNode.next = null;
                                head.next = childNode;
                                head = childNode;
                            }
                            root.rbTree = null;
                            root.node = temp;
                        }
                        ChildNode optNode = root.node;

                        while (optNode != null) {
                            //创建新节点
                            ChildNode newOptNode = new ChildNode();
                            newOptNode.key = optNode.key;
                            newOptNode.value = optNode.value;
                            //插入到新的数组中
                            Object key = optNode.key;
                            int index = hash(key, newCapacity);
                            //判断是否是空
                            if (newNodes[index].node == null) {
                                newNodes[index].node = newOptNode;
                            } else {
                                ChildNode tempNode = newNodes[index].node;
                                while (tempNode != null) {
                                    ChildNode nodeSwap = tempNode.next;
                                    if (nodeSwap == null) {
                                        break;
                                    }
                                    tempNode = nodeSwap;
                                }
                                if (tempNode == null) {
                                    newNodes[index].node = newOptNode;
                                } else {
                                    tempNode.next = newOptNode;
                                }
                            }
                            newNodes[index].length++;
                            optNode = optNode.next;
                        }
                    }
                    this.nodes = newNodes;
                    this.capacity = newCapacity;
                }
            } finally {
                reentrantReadWriteLock.writeLock().unlock();
            }
        }
    }

    //识别红黑树和链表查找key
    private V getInside(K key) {
        int index = hash(key);
        Root<K,V>  root = this.nodes[index];
        if (root.rbTree != null) {
            return getTree(key,root);
        } else if (root.node != null){
            return getNode(key,root);
        }
        return null;
    }

    private V getNode(K key,Root<K,V>  root) {
        ChildNode<K, V> optNode = root.node;
        while (optNode != null) {
            if (optNode.key.equals(key)) {
                return optNode.value;
            }
            optNode = optNode.next;
        }
        return null;
    }

    private V getTree(K key,Root<K,V> root) {
        RBTree<ChildNode<K, V>>.RBTNode<ChildNode<K, V>> search = root.rbTree.search(new ChildNode<>(key));
        if (search != null) {
            return search.getKey().value;
        }
        return null;
    }


    //根据节点长度自动转换为红黑树或者链表
    private void autoChange(Root<K, V> root) {
        if (root.length > 8 && root.rbTree == null&&root.node!=null) {
            toRBTree(root);
        } else if (root.length < 6 && root.node == null&&root.rbTree!=null) {
            toNode(root);
        }
    }


    //转换为红黑树
    private void toRBTree(Root<K, V> root) {
        RBTree<ChildNode<K, V>> rbTree = new RBTree<>();
        ChildNode<K, V> optNode = root.node;
        while (optNode != null) {
            rbTree.insert(optNode);
            optNode = optNode.next;
        }
        root.rbTree = rbTree;
        root.node = null;
    }

    //转换为链表
    private void toNode(Root<K, V> root) {
        RBTree<ChildNode<K, V>> rbTree = root.rbTree;
        List<ChildNode<K, V>> list = rbTree.toList();
        ChildNode<K, V> head = new ChildNode<>();
        head.key = list.get(0).key;
        head.value = list.get(0).value;
        ChildNode<K, V> temp = head;
        for (int i = 1; i < list.size(); i++) {
            ChildNode<K, V> childNode = list.get(i);
            childNode.next = null;
            head.next = childNode;
            head = childNode;
        }
        root.rbTree = null;
        root.node = temp;
    }
    public V put(K key, V value) {
       return putInside(key, value);
    }

    @Override
    public V get(Object key) {
        return getInside((K) key);
    }

    @Override
    public int size() {
        return this.size.get();
    }


    @Override
    public boolean isEmpty() {
        return this.size.get() == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        int index = hash(key);
        Root node = this.nodes[index];
        //判断是否是红黑树
        if (node.rbTree != null) {
            return node.rbTree.search(new ChildNode<>((K) key)) != null;
        }else if (node.node != null){
            ChildNode optNode = node.node;
            while (optNode != null) {
                if (optNode.value.equals(key)) {
                    return true;
                }
                optNode = optNode.next;
            }
        }
        return false;
    }



    @Override
    public void clear() {
        try {
            reentrantReadWriteLock.writeLock().lock();
            nodes = new Root[capacity];
            size.set(0);
        }finally {
            reentrantReadWriteLock.writeLock().unlock();
        }
    }

    @Override
    public Set<K> keySet() {
        Set<K> set = new HashSet<>();
        for (Root<K, V> node : this.nodes) {
            if (node.rbTree != null) {//红黑树
                node.rbTree.toList().forEach((childNode) -> {
                    set.add(childNode.key);
                });
            } else if (node.node != null){
                ChildNode<K, V> optNode = node.node;
                while (optNode != null) {
                    set.add((K) optNode.key);
                    optNode = optNode.next;
                }
            }
        }
        return set;
    }

    @Override
    public Collection<V> values() {
        List<V> list = new ArrayList<>();
        for (Root<K, V> root : this.nodes) {
            if (root.rbTree != null) {
                root.rbTree.toList().forEach((childNode) -> {
                    list.add(childNode.value);
                });
            } else if (root.node != null){
                ChildNode<K, V> optNode = root.node;
                while (optNode != null) {
                    list.add(optNode.value);
                    optNode = optNode.next;
                }
            }
        }
        return list;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> set = new HashSet<>();
        for (Root<K, V> node : this.nodes) {
            if (node.rbTree != null) {
                node.rbTree.toList().forEach((childNode) -> {
                    set.add(new AbstractMap.SimpleEntry<>((K) childNode.key, childNode.value));
                });
            } else if (node.node != null) {
                ChildNode<K, V> optNode = node.node;
                while (optNode != null) {
                    set.add(new AbstractMap.SimpleEntry<>((K) optNode.key, optNode.value));
                    optNode = optNode.next;
                }
            }
        }
        return set;
    }

    @Override
    public boolean containsValue(Object value) {
        throw new UnsupportedOperationException("不支持的操作");
    }
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        throw new UnsupportedOperationException("不支持的操作");
    }
    public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        throw new UnsupportedOperationException("不支持的操作");
    }

    @Override
    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        throw new UnsupportedOperationException("不支持的操作");
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        throw new UnsupportedOperationException("不支持的操作");
    }





}
